package com.c2b.algorithm.newcoder.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href=">二叉树中和为某一值的路径(一)</a>
 * <p>
 * 给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。<br>
 * 1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点<br>
 * 2.叶子节点是指没有子节点的节点<br>
 * 3.路径只能从父节点到子节点，不能从子节点到父节点<br>
 * 4.总节点数目为n<br>
 * </p>
 *
 * @author c2b
 * @since 2023/3/14 11:21
 */
public class BM0029HasPathSum_S {

    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        final Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            final TreeNode currNode = queue.poll();
            if (currNode.val == sum && currNode.left == null && currNode.right == null) {
                return true;
            }
            if (currNode.left != null) {
                currNode.left.val = currNode.val + currNode.left.val;
                queue.offer(currNode.left);
            }
            if (currNode.right != null) {
                currNode.right.val = currNode.val + currNode.right.val;
                queue.offer(currNode.right);
            }
        }
        return false;
    }

    public boolean hasPathSum2(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null && sum == root.val) {
            return true;
        }
        return hasPathSum2(root.left, sum - root.val) || hasPathSum2(root.right, sum - root.val);
    }

    public static void main(String[] args) {
        BM0029HasPathSum_S bm0029HasPathSum_s = new BM0029HasPathSum_S();
        TreeNode node = new TreeNode(5);
        node.left = new TreeNode(4);
        node.right = new TreeNode(8);
        node.left.left = new TreeNode(1);
        node.left.right = new TreeNode(11);
        node.right.right  = new TreeNode(9);
        node.left.right.left = new TreeNode(2);
        node.left.right.right = new TreeNode(7);
        System.out.println(bm0029HasPathSum_s.hasPathSum(node, 22));
    }
}
